/*
2021-10-26 
https://leetcode-cn.com/problems/count-nodes-with-the-highest-score/
*/
typedef long long ll;
const int N=100010;
int sum[N];
vector<int> edge[N];
class Solution {
public:
    int res = 0;
    ll maxv = -1;
    int tot;

    void dfs(int u)
    {
        ll cur=1;
        sum[u]=1;

        for(auto t:edge[u])
        {
            dfs(t);
            sum[u]+=sum[t];
            cur*=sum[t];
        }

        if(sum[u]<tot) cur=cur*(tot-sum[u]);

        if(cur>maxv)
        {
            maxv=cur;
            res=0;
        }
        if(cur==maxv) res++;
    }

    int countHighestScoreNodes(vector<int>& parents) {
        int n=parents.size();
        
        res=0;
        maxv=-1;
        tot=n;

        for(int i=0;i<=n;i++) edge[i].clear();

        for(int i=1;i<n;i++)
            edge[parents[i]].push_back(i);
        dfs(0);
        return res;
    }
};
